﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/implement-stack-using-queues/
/*
题目描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 

注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 

示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
 

提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
 

进阶：你能否仅用一个队列来实现栈。
*/


// 重定义数据类型
typedef int QDataType;

// 定义节点类型
typedef struct QueueNode {
	struct QueueNode* next;
	QDataType data;
} QueueNode;

// 定义队列类型
typedef struct Queue {
	QueueNode* head;
	QueueNode* tail;
} Queue;

// 队列的初始化
void QueueInit(Queue* pq);

// 队列的入队
void QueuePush(Queue* pq, QDataType x);

// 队列的出队
void QueuePop(Queue* pq);

// 返回队列的对头元素
QDataType QueueFront(Queue* pq);

// 返回队列的队尾元素
QDataType QueueBack(Queue* pq);

// 返回队列中的节点个数
int QueueSize(Queue* pq);

// 判断队列是否为空
bool QueueEmpty(Queue* pq);

// 销毁队列
void QueueDestroy(Queue* pq);

// 队列的初始化
void QueueInit(Queue* pq) {
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

// 队列的入队
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	// 创建一个新节点
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newNode) {
		perror("malloc fail!\n");
		exit(-1);
	}
	newNode->data = x;
	if (NULL == pq->head) {
		pq->head = newNode;
		pq->tail = newNode;
		pq->tail->next = NULL;
	}
	else {
		pq->tail->next = newNode;
		pq->tail = pq->tail->next;
		pq->tail->next = NULL;
	}
}

// 队列的出队
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	// 如果对头为空了，我们也要把队尾也给置空，避免野指针
	if (NULL == pq->head) {
		pq->tail = NULL;
	}
}

// 返回队列的对头元素
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

// 返回队列的队尾元素
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

// 返回队列中的节点个数
int QueueSize(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* cur = pq->head;
	int size = 0;
	while (cur) {
		size++;
		cur = cur->next;
	}
	return size;
}

// 判断队列是否为空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head == NULL;
}

// 销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* cur = pq->head;
	QueueNode* next = cur->next;
	while (cur) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}







typedef struct {
	Queue queue1;
	Queue queue2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
	if (NULL == stack) {
		perror("malloc fail!\n");
		exit(-1);
	}
	QueueInit(&stack->queue1);
	QueueInit(&stack->queue2);
	return stack;
}

void myStackPush(MyStack* obj, int x) {
	// 压栈我们要把数据入到不为空的队列的队尾
	Queue* NonEmptyQueue = &obj->queue1; // 默认queue1队列不为空
	Queue* EmptyQueue = &obj->queue2;
	if (QueueEmpty(&obj->queue1)) { // 如果队列1为空，我们就要替换一下
		NonEmptyQueue = &obj->queue2;
	}
	// 将数据入到不为空的队列
	QueuePush(NonEmptyQueue, x);
}

int myStackPop(MyStack* obj) {
	// 弹栈我们要先将不为空的队列先执行出队操作，并将数据入到为空的那个栈中，
	// 直到不为空的队列出到队列中只剩一个元素
	Queue* NonEmptyQueue = &obj->queue1; // 默认queue1队列不为空
	Queue* EmptyQueue = &obj->queue2;
	if (QueueEmpty(&obj->queue1)) { // 如果队列1为空，我们就要替换一下
		NonEmptyQueue = &obj->queue2;
		EmptyQueue = &obj->queue1;
	}
	while (QueueSize(NonEmptyQueue) > 1) {
		// 先保存队头元素的值
		int temp = QueueFront(NonEmptyQueue);
		QueuePop(NonEmptyQueue);
		QueuePush(EmptyQueue, temp);
	}
	int returnVal = QueueFront(NonEmptyQueue);
	QueuePop(NonEmptyQueue);
	return returnVal;
}

int myStackTop(MyStack* obj) {
	Queue* NonEmptyQueue = &obj->queue1; // 默认queue1队列不为空
	Queue* EmptyQueue = &obj->queue2;
	if (QueueEmpty(&obj->queue1)) { // 如果队列1为空，我们就要替换一下
		NonEmptyQueue = &obj->queue2;
		EmptyQueue = &obj->queue1;

	}
	return QueueBack(NonEmptyQueue);
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2);

}

void myStackFree(MyStack* obj) {
	// 先要销毁队列，因为我们始终保持着一个队列为空，所以销毁只需要销毁空的那个队列即可
	if (!myStackEmpty(obj)) { // 如果栈不为空，那我们就要先销毁队列
		Queue* NonEmptyQueue = &obj->queue1; // 默认queue1队列不为空
		Queue* EmptyQueue = &obj->queue2;
		if (QueueEmpty(&obj->queue1)) { // 如果队列1为空，我们就要替换一下
			NonEmptyQueue = &obj->queue2;
			EmptyQueue = &obj->queue1;

		}
		QueueDestroy(NonEmptyQueue);
	}
	// 再销毁栈
	free(obj);
	obj = NULL;
}

int main() {
	MyStack *stack = myStackCreate();
	/*myStackPush(stack, 1);
	myStackPush(stack, 2);
	myStackPop(stack);*/
	bool flag = myStackEmpty(stack);

	printf("%d\n", flag);
	myStackFree(stack);

	return 0;
}